import java.util.Stack;

public class ReversePrint {

    // 递归方式
    public static void printListRecursive(Node head) {
        if (null != head) {          // 基本情况：如果当前节点不为空
            printListRecursive(head.next);  // 递归调用，先处理下一个节点
            System.out.print(head.val + " "); // 等递归返回后再打印当前节点值
        }
    }

    // 循环方式
    public static void printListIterative(Node head) {
        if (null == head) {          // 处理空链表情况
            return;               // 直接返回
        }

        Stack<Node> stack = new Stack<>(); // 创建一个栈来存储节点

        // 将链表中的结点保存在栈中
        Node current = head;          // 从链表头开始
        while (null != current) {       // 遍历整个链表
            stack.push(current);          // 将当前节点压入栈中
            current = current.next;       // 移动到下一个节点
        }

        // 将栈中的元素出栈
        while (!stack.empty()) {        // 当栈不为空时
            System.out.print(stack.pop().val + " "); // 弹出栈顶元素并打印其值
        }
    }

    public static void main(String[] args) {
        // 创建测试链表 1->2->3->4
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);

        System.out.println("递归方式逆序打印:");
        printListRecursive(head);
        /*输出：
        递归方式逆序打印:
        4 3 2 1*/

        System.out.println("\n循环方式逆序打印:");
        printListIterative(head);
        /*输出：
        循环方式逆序打印:
        4 3 2 1*/
    }
}
